package com.xizi.sort;

public class 归并排序 {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int n = arr.length;
        System.out.print("排序前：");
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
        //归并排序
        merge_sort(arr, 0, n - 1);
        System.out.print("排序后：");
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }

    public static void merge_sort(int[] arr, int left, int right) {
        //递归结束条件
        if (left >= right) {
            return;
        }
        //先分
        int mid = (left + right) >> 1;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        //临时数组, 用于临时存储 [l,r]区间内排好序的数据
        int[] tmp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        //再合
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
        }
        //当其中一个遍历完毕后 另一个还剩余元素 全部添加到tmp中
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        //当前[left,right]已排序的数还给arr数组
        for (i = left, j = 0; i <= right; i++, j++) {
            arr[i] = tmp[j];
        }
    }
}